package knapsackga;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import knapsackga.FitnessFunction.FitnessComparator;

/**
 * Main Knapsack GA class. Handles the main GA loop.
 * 
 * @author nathaniel and curtis
 */
public class KnapsackGA {
	private Knapsack knapsack = null;

	private FitnessFunction fitness_function = null;

	private double crossover_probability = .9;

	private double clone_probability = .1;

	private double bit_mutation_probability = .01;

	private double _epsilon = 0.1d;

	public KnapsackGA(Knapsack knapsack, FitnessFunction fitness_function) {
		this.fitness_function = fitness_function;
		this.knapsack = knapsack;
	}

	public Double[][] start(int population_size, int number_of_generations) {
		Double[][] fitness_values = new Double[number_of_generations][population_size];

		/* Create the initial population */
		List<Genome> population = new ArrayList<Genome>();
		for (int i = 0; i < population_size; i++) {
			population.add(new Individual(knapsack, fitness_function));
		}

		/* main generational loop */
		for (int generation = 0; generation < number_of_generations; generation++) {
			/* evaluate the population and get the total fitness */
			double total_fitness = evaluatePopulation(population);
			Collections.sort(population, new FitnessComparator());

			for (int idx = 0; idx < population_size; idx++) {
				fitness_values[generation][idx] = population.get(idx)
						.getFitness();
			}

			/* begin to build our new population */
			List<Genome> new_population = new ArrayList<Genome>();

			/* keep adding new genomes till we have filled the new population */
			while (new_population.size() < population_size) {
				/* figure out what kind of breeding we are doing */
				double breed_type = Math.random();
				if (breed_type < clone_probability) {
					/*
					 * grab genome and clone it
					 */
					Genome g = select(population);// , total_fitness);
					new_population.add(g.makeClone());

				} else if (breed_type < (clone_probability + crossover_probability)) {
					/*
					 * grab two parents to cross over and add their children to
					 * the new population.
					 */
					Genome parent_a = select(population);
					// ,total_fitness);
					Genome parent_b = select(population);
					// ,total_fitness);

					List<Genome> children = parent_a.crossover(parent_b);
					for (Genome child : children) {
						/* mutate the child before adding it into the population */
						child.mutate(bit_mutation_probability);
						new_population.add(child);
					}
				}
			}

			// System.out.println( "Best: " + population.get( 0 ) );

			/* replace the old generation with the new one and start all over */
			population = new_population;
		}

		return fitness_values;
	}

	/**
	 * Evaluate the fitness of the passed in population and return the total
	 * fitness of the population.
	 * 
	 * @param population
	 *            the population of genomes to evaluate
	 * @return the total fitness of every genome in the population
	 */
	private double evaluatePopulation(List<Genome> population) {
		double total = 0;

		for (Genome g : population) {
			total += g.getFitness();
		}

		return total;
	}

	public Genome select(List<Genome> population) {
		return selectTournament(population);
	}

	public Genome selectTournament(List<Genome> population) {
		int tournament_size = 7;

		double best_fitness = Double.NEGATIVE_INFINITY;
		Genome best = null;
		for (int i = 0; i < tournament_size; i++) {
			int index = (int) (population.size() * Math.random());
			if (population.get(index).getFitness() > best_fitness) {
				best = population.get(index);
				best_fitness = best.getFitness();

			}
		}

		return best;
	}

	/**
	 * Using Roulette Selection select an individual from the population.
	 * 
	 * @param population
	 *            the population of genomes to select one from
	 * @return a genome selected from the population
	 */
	public Genome selectRoulette(List<Genome> population) {
		// Reimplemented by Curtis 09-08-07
		// Name a variable for a genome to return
		Genome selectedGenome = null;
		// Get the minimum fitness and the maximum fitness
		double minFitness = Double.POSITIVE_INFINITY;

		for (int i = 0; i < population.size(); i++) {
			double thisFitness = population.get(i).getFitness();
			if (thisFitness < minFitness) {
				minFitness = thisFitness;
			}

		}
		// Get the total fitness range
		// Adjust the fitness to make all values positive and account for
		// epsilon
		double totalAdjustedFitness = population.size()
				* (_epsilon - minFitness);
		for (int i = 0; i < population.size(); i++) {
			// Add up all of the fitnesses of the individuals
			totalAdjustedFitness = population.get(i).getFitness()
					+ totalAdjustedFitness;
		}

		// Generate our random number in the fitness range
		double rouletteFitness = Math.random() * totalAdjustedFitness;
		// Save the value of the running total
		double runningTotal = 0d;
		// Go through the genomes to find out where we where our random number
		// landed
		for (int j = 0; j < population.size(); j++) {
			// Subtract the minimum fitness in each genome to normalize the
			// values
			double thisFitness = population.get(j).getFitness() - minFitness;
			if (rouletteFitness <= (_epsilon + runningTotal + thisFitness)) {
				selectedGenome = population.get(j);
				break;
			}
			// Add to the running total
			runningTotal = _epsilon + thisFitness + runningTotal;
		}
		return selectedGenome;
	}
}
